"""
题目：判断一棵二叉树是否为平衡二叉树（每个节点的左右两个子树的高度差的绝对值不超过 1）。
"""


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_balanced(root):
    """判断二叉树是否为平衡二叉树"""

    def check_depth(node):
        # 空节点深度为0
        if not node:
            return 0

        # 计算左子树深度，如果不平衡返回-1
        left_depth = check_depth(node.left)
        if left_depth == -1:
            return -1

        # 计算右子树深度，如果不平衡返回-1
        right_depth = check_depth(node.right)
        if right_depth == -1:
            return -1

        # 检查当前节点的左右子树高度差
        if abs(left_depth - right_depth) > 1:
            return -1  # 不平衡

        # 返回当前节点的深度
        return 1 + max(left_depth, right_depth)

    # 如果返回值不是-1，则为平衡二叉树
    return check_depth(root) != -1


# 辅助函数：创建二叉树（复用）
def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root


# 测试
# 平衡树
root1 = create_binary_tree([3, 9, 20, None, None, 15, 7])
print(is_balanced(root1))  # 输出: True

# 不平衡树（右子树过深）
root2 = create_binary_tree([1, 2, 2, 3, 3, None, None, 4, 4])
print(is_balanced(root2))  # 输出: False
